//import java.sql.SQLOutput;
//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        char[] s = in.nextLine().toCharArray();
//        int n = s.length;
//        for(int i = 0; i < n / 2; i++){
//            char tmp = s[i];
//            s[i] = s[n - 1 - i];
//            s[n - 1 - i] = tmp;
//        }
//        int k = in.nextInt();
//        int[][] g = new int[n][n];
//        for(int i = n - 2; i >= 0; i--){
//            for(int j = i + 1; j < n; j++){
//                g[i][j] = g[i+1][j-1] + (s[i] == s[j] ? 0 : 1);
//            }
//        }
//        int[][] f = new int[k][n];
//        f[0] = g[0];
//        int mn = 0;
//        int[][] ans = new int[k][n];
//        ans[0][0] = n-1;
//        int[][] from = new int[k][n];
//        for(int i = 1; i < k; i++){
//            for(int r = i; r < n; r++){
//                int res = Integer.MAX_VALUE;
//                for(int l = i; l <= r; l++){
//                    if(res > f[i-1][l-1] + g[l][r]){
//                        res = f[i-1][l-1] + g[l][r];
//                        from[i][r] = l;
//                    }
//                }
//                f[i][r] = res;
//            }
//            if(f[mn][n-1] > f[i][n-1]){
//                mn = i;
//                ans = from;
//            }
//        }
//
//        System.out.println(f[mn][n-1]);
//        int l = n, r = n - 1;
//        for(int i = mn; i >= 0; i--){
//            r = l - 1;
//            l = ans[i][r];
//            System.out.print(print(l, r, s));
//            if(i > 0)
//                System.out.print("+");
//        }
//        //7
//        //a+b+cabcaacbac+xyzxyzzyxzyx
//        System.out.println();
//    }
//    static String print(int ll, int rr, char[] s){
//        int l = ll, r = rr;
//        while(l < r){
//            s[l] = s[r];
//            l++;
//            r--;
//        }
//        return new String(s, ll, rr-ll+1);
//    }
//}
//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        List<Integer>[] g = new ArrayList[n];
//        Arrays.setAll(g, e->new ArrayList<>());
//        for(int i = 0; i < n - 1; i++){
//            int x = in.nextInt()-1, y = in.nextInt()-1;
//            g[x].add(y);
//            g[y].add(x);
//        }
//        //a + b = n - 1
//        has = new boolean[n];
//        dfs(0, -1, g);
//        has[0] = false;
//        int total = 0;
//        for(boolean x : has){
//            if(x) total++;
//        }
//        System.out.println(total);
//        for(int i = 1; i < n; i++){
//            if(has[i]){
//                System.out.println(i + " " + (n - 1 - i));
//            }
//        }
//    }
//    static boolean[] has;
//    static int dfs(int x, int fa, List<Integer>[] g){
//        int size = 1, sz = 0;
//        int n = g.length;
//        boolean[] f = new boolean[n];
//        f[0] = true;
//        for(int y : g[x]){
//            if(y == fa) continue;
//            sz = dfs(y, x, g);
//            for(int j = n - 2; j >= sz; j--){
//                f[j] = f[j] || f[j - sz];
//            }
//            size += sz;
//        }
//        sz = n - size;
//        for(int j = n - 2; j >= sz; j--){
//            f[j] = f[j] || f[j - sz];
//        }
//        for(int i = 0; i < n; i++){
//            if(f[i]){
//                has[i] = true;
//            }
//        }
//        return size;
//    }
//}
//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
//        int mod = (int)1e9+7;
//        if(k != 1) System.out.println(m);
//        else{
//            int cnt = (n + 1) / 2;
//            long res = 1;
//            long x = n;
//            while(cnt > 0){
//                if(cnt%2==1) res = res * x % mod;
//                x = x * x % mod;
//                cnt /= 2;
//            }
//            System.out.println(res);
//        }
//    }
//}
//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int[] a = new int[n];
//        for(int i = 0; i < n; i++){
//            a[i] = in.nextInt();
//        }
//        List<int[]> time = new ArrayList<>();
//        int i = 0;
//        int ans = 0;
//        while(i < n){
//            int j = i + 1;
//            while(j < n && a[j] > a[j-1]){
//                j++;
//            }
//            ans = Math.max(ans, j - i);
//            time.add(new int[]{i, j-1});
//            i = j;
//        }
//        ans = Math.min(ans + 1, n);
//        for(i = 1; i < time.size(); i++){
//            int l = time.get(i-1)[1];
//            //l + 1 -> r
//            int r = time.get(i)[1];
//            if(r == l + 1 || a[l+2] - a[l] > 1 || time.get(i-1)[0] == l || a[l+1] - a[l-1] > 1){
//                ans = Math.max(ans, r - time.get(i-1)[0] + 1);
//            }
//        }
//        System.out.println(ans);
//    }
//}
//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int T = in.nextInt();
//        while(T-- > 0){
//            int n = in.nextInt();
//            int m = in.nextInt();
//            long[] ans = new long[n];
//            long[][] pre = new long[n][m+1];
//            for(int i = 0; i < n; i++){
//                for(int j = 0; j < m; j++){
//                    pre[i][j+1] = pre[i][j] + in.nextInt();
//                }
//                ans[i] = pre[i][m];
//            }
//            Integer[] idx = new Integer[n];
//            Arrays.setAll(idx, i->i);
//            Arrays.sort(idx, (x, y) -> Long.compare(ans[y],ans[x]));
//            long res = 0;
//            for(int i = 0; i < n; i++){
//                int k = idx[i];
//                for(int j = 0; j < m; j++){
//                    res += pre[k][j+1];
//                }
//                res += (n - i - 1) * m * pre[k][m];
//            }
//            System.out.println(res);
//        }
//    }
//}
//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int[] a = new int[n];
//        for(int i = 0; i < n; i++){
//            a[i] = in.nextInt();
//        }
//        in.nextLine();
//        int[][] f = new int[n][n];
//        long[][] g = new long[n][n];
//        for(int i = 0; i < n; i++){
//            char[] s = in.nextLine().toCharArray();
//            for(int j = 0; j < n; j++){
//                if(s[j] == 'Y'){
//                    f[i][j] = 1;
//                    g[i][j] = a[i] + a[j];
//                }
//            }
//        }
//        for(int k = 0; k < n; k++){
//            for(int i = 0; i < n; i++){
//                if(i == k) continue;
//                for(int j = 0; j < n; j++){
//                    if(j == k || i == j || f[i][j] == 1) continue;
//                    if(f[i][k] != 0 && f[k][j] != 0) {
//                        int res = f[i][j] == 0 ? Integer.MAX_VALUE : f[i][j];
//                        int res2 = f[i][k] + f[k][j];
//                        if(res > res2 || res == res2 && g[i][j] < g[i][k] + g[k][j] - a[k]){
//                            res = res2;
//                            g[i][j] = g[i][k] + g[k][j] - a[k];
//                        }
//                        f[i][j] = res;
//                    }
//                }
//            }
//        }
//        int q = in.nextInt();
//        for(int i = 0; i < q; i++){
//            int x = in.nextInt() - 1, y = in.nextInt() - 1;
//            if(f[x][y] == 0) System.out.println("Impossible");
//            else{
//                System.out.println(f[x][y] + " " + g[x][y]);
//            }
//        }
//    }
//}

//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        char[] s = in.nextLine().toCharArray();
//        int[] cnt = new int[26];
//        for(char c : s){
//            if(++cnt[c-'a']==100){
//                System.out.println(String.valueOf(c).repeat(100));
//                return;
//            }
//        }
//        int n = s.length;
//        int[][] f = new int[n][n];
//        for(int i = n - 1; i >= 0; i--){
//            f[i][i] = 1;
//            for(int j = i + 1; j < n; j++){
//                if(s[i]==s[j]){
//                    f[i][j] = 2 + f[i+1][j-1];
//                }else{
//                    f[i][j] = Math.max(f[i+1][j], f[i][j-1]);
//                }
//            }
//        }
//        StringBuilder t = new StringBuilder();
//        int i = 0, j = n - 1;
//        while(i < j && t.length() < 50){
//            if(s[i] == s[j]){
//                t.append(s[i]);
//                i++;
//                j--;
//            }else if(f[i][j] == f[i+1][j]){
//                i++;
//            }else{
//                j--;
//            }
//        }
//        StringBuilder t2 = new StringBuilder(t);
//        t2.reverse();
//        if(i == j && t.length() < 50)
//            t.append(s[i]);
//        System.out.println(t.toString() + t2);
//    }
//}

//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int m = in.nextInt();
//        if(m > n){
//            System.out.println(-1);
//        }else{
//            int[] f = new int[n+1];
//            f[1] = 1;
//            for(int i = 2; i <= n; i++){
//                f[i] = Math.min(f[i-1], f[i-2]) + 1;
//            }
//            System.out.println(Arrays.toString(f));
//            System.out.println((f[n]+m-1)/m * m);
//        }
//    }
//}
//import java.util.*;
//public class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int m = in.nextInt();
//        in.nextLine();
//        char[] s = in.nextLine().toCharArray();
//        char[] t = in.nextLine().toCharArray();
//        int[] L = new int[m];
//        int[] R = new int[m];
//        int j = 0;
//        for(int i = 0; i < m; i++){
//            while(s[j] != t[i]){
//                j++;
//            }
//            L[i] = j;
//            j++;
//        }
//        j = n - 1;
//        for(int i = m - 1; i >= 0; i--){
//            while(s[j] != t[i]){
//                j--;
//            }
//            R[i] = j;
//            j--;
//        }
//        System.out.println(Arrays.toString(L));
//        System.out.println(Arrays.toString(R));
//        int ans = 0;
//        for(int i = 0; i < m - 1; i++){
//            ans = Math.max(ans,
//                    Math.max(L[i+1]-L[i],
//                            Math.max(R[i+1]-R[i], R[i+1]-L[i])));
//        }
//        System.out.println(ans);
//    }
//}
import java.util.*;
class Fenwick{
    Info[] f;
    public record Info(int mx, int w, int mx1, int w1){

    }
    public Fenwick(int[] a){
        int n = a.length;
        f = new Info[n<<2];
        build(1, 0, n-1, a);
    }
    void build(int i, int l, int r, int[] a){
        if(l == r){
            f[i] = new Info(a[l], 1, 0, 0);
            return;
        }
        int mid = (l + r) / 2;
        build(i<<1, l, mid, a);
        build(i<<1|1, mid+1, r, a);
        maintain(i);
    }
    Info merge(Info a, Info b){
        int mx, mx1, w, w1;
        if(a.mx == b.mx){
            mx = a.mx;
            w = a.w + b.w;
            if(a.mx1 == b.mx1){
                mx1 = a.mx1;
                w1 = a.w1 + b.w1;
            }else if(a.mx1 > b.mx1){
                mx1 = a.mx1;
                w1 = a.w1;
            }else{
                mx1 = b.mx1;
                w1 = b.w1;
            }
        }else if(a.mx > b.mx){
            mx = a.mx;
            w = a.w;
            if(b.mx == a.mx1){
                mx1 = b.mx;
                w1 = b.w + a.w1;
            }else if(b.mx > a.mx1){
                mx1 = b.mx;
                w1 = b.w;
            }else{
                mx1 = a.mx1;
                w1 = a.w1;
            }
        }else{
            mx = b.mx;
            w = b.w;
            if(a.mx == b.mx1){
                mx1 = a.mx;
                w1 = a.w + b.w1;
            }else if(a.mx > b.mx1){
                mx1 = a.mx;
                w1 = a.w;
            }else{
                mx1 = b.mx1;
                w1 = b.w1;
            }
        }
        return new Info(mx, w, mx1, w1);
    }
    void maintain(int i){
        f[i] = merge(f[i<<1], f[i<<1|1]);
    }
    void update(int i, int l, int r, int j, int val){
        if(l == r){
            f[i] = new Info(val, 1, 0, 0);
            return;
        }
        int mid = (l + r) / 2;
        if(j <= mid){
            update(i<<1, l, mid, j, val);
        }else{
            update(i<<1|1, mid+1, r, j, val);
        }
        maintain(i);
    }
    Info query(int i, int l, int r, int jobl, int jobr){
        if(jobl <= l && r <= jobr){
            return f[i];
        }
        int mid = (l + r) / 2;
        if(jobr <= mid){
            return query(i<<1, l, mid, jobl, jobr);
        }
        if(jobl > mid){
            return query(i<<1|1, mid+1, r, jobl, jobr);
        }
        Info a = query(i<<1, l, mid, jobl, jobr);
        Info b = query(i<<1|1, mid+1, r, jobl, jobr);
        return merge(a, b);
    }
}
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = in.nextInt();
        }
        Fenwick f = new Fenwick(a);
        for(int i = 0; i < q; i++) {
            int op = in.nextInt();
            int l = in.nextInt()-1;
            int r = in.nextInt();
            if (op == 1) {
                f.update(1, 0, n-1, l, r);
            } else {
                Fenwick.Info res = f.query(1, 0, n-1, l, r-1);
                System.out.println(res.w1());
            }
        }
    }
}